坤坤的代码〇
实质上是模意义下斐波那契数列求和，注意到模数很小容易出现循环。
1 | from functools import reduce |
坤坤的代码Ⅰ
$\sum_{i|n}^{n\in[1,10^7]}1=\sum_{i=1}^{10^7}\lfloor\frac{10^7}{i}\rfloor$
1 | n = 10000000 |
坤坤的代码Ⅱ
使用 MillerRabin 算法重写 is_prime 即可
1 | from random import randint |
坤坤的代码Ⅲ
求满足 $i\in[1,n],i^{\varphi(n)}\equiv1(\mod n),\gcd(i,n)=1,\forall j\in[1,\varphi(n)),i^j\not\equiv1(\mod n)$ 的 $i$ 之和。
根据欧拉定理：$\gcd(i,n)=1\Rightarrow i^{\varphi(n)}\equiv1(\mod n)$.
实际上，$67108934=2\times33554467$ ，故很容易排除 $\gcd(i,n)\neq1$ 的 $i$.
那只要再排除 $\exist j\in[1,\varphi(n)),i^j\equiv1(\mod n)$ 的 $i$ 即可；
注意到 $\varphi(n)=33554466=2\times3^3\times11\times56489$ 且对于一个 $i$, $\forall d>1,d|\varphi(n), \exist j=\frac{\varphi(n)}{d}\in[1,\varphi(n)),(i^d)^j\equiv1(\mod n)$ ，则可以排除 $i^d$
1 | n = 67108934 |
坤坤的代码Ⅳ
注意到题目要求的式子$\sum_{b\in\text{product}(a,2^n)}^{Q|\sum b_i}\prod b_i$可由两个 $\text{repeat}=2^n$ 合并为 $\text{repeat}=2^{n+1}$ ，整体的思路就是求出 $\text{repeat}=2^n$ 时的值，对 $\text{repeat}\neq2^n$ 的情况分解为多个二次幂之和求解，此做法是ⅠⅡⅢ的通解。
问题在于如何合并。首先原式是低效的枚举判断形式，为了高效找出符合 $Q|\sum b_i$ 的 $b_i$ 就要考虑按 $\sum b_i \mod Q$ 分类 以便合并；其次先求积再求和使得必须枚举 ，不如先求和再求积。
设
$$
f_{n,r}=\sum_{b\in \text{product}(a,2^{n})}^{\sum b_i\equiv r(\mod Q) }\prod b_i
$$
则有
$$
f_{n+1,r}=\sum_{i=0}^{Q-1}f_{n,i}f_{n,Q-i(\mod i)}
$$
$n$ 不等的 $f$ 也是一样方法合并
1 | P = 0x7fffffff |
坤坤的帅气签名
使用 CRT 加速 RSA 签名时， $c$ 通过 $c_p\equiv m^d(\mod p),c_q\equiv m^d(\mod q)$ 合并得到。
不妨假设在计算 $c_p$ 时出现错误得到一个错误值 $c_p’\neq c_p$ 而 $c_q$ 是正确的。
记由 $c_p’,c_q$ 合并出来的值为 $c’$，则有
$$
q=\gcd((c’^e-m)\mod n,n)
$$
1 | from math import gcd |
Classical
首先枚举 key_size , 计算按当前 key_size 将 cipher_text 分割，用 hamming_distance 量化各个 key_size 的可能性，从而得出最可能的 key_size. 之后将按确定的 key_size 分组的 cipher_text 每组相应位置分别取出串联成重组串，在用频率攻击解决 singlechar_xor 问题即可。
1 | from base64 import b64decode |
KUNKUN’s Oracle
Ⅰ
由两个同余方程可以得到两个 $X,n|(X^2-a)$，那么 $n|gcd(X_1^2-a,X_2^2-a)$
不妨假设 $n=gcd(X_1^2-a,X_2^2-a)$ 求出 flag_one_int 发现每次结果相同，flag_one 为 cnss{Gu3ss_n_1s_s0_e4sy}
Ⅱ
模数为 $n=pq$ 的二次同余方程有 $4$ 解或无解。
为简化此问题，不如考虑 $a=1$ 的情况：
对 $$X^2\equiv 1(\mod n)\tag{1}$$ 显然有 $1,n-1$ 两解，且剩余两解在模意义下互为相反数。
考虑方程
$$
X^2\equiv1(\mod p)\tag{2}\
$$
$$
X^2\equiv1(\mod q)\tag{3}
$$
对于 $(1)$ 的任意一个非平凡解 $X$ 都满足 $(2),(3)$，即有 $p|X\pm1,q|X\mp1$，那么 $\gcd(X-1,n)\neq1$，由此可得 $p$ 或 $q$ .
1 | from random import randint |
Linear Fucking Shit Register
经典的 LFSR 已知长度 $2m$ 加密数据流推出 mask 的问题
$2m$ 个位之间可列出 $m$ 元一次模 $2$ 意义下线性方程组，可借助矩阵求逆求解，但本题所给数据得出的系数矩阵是奇异的，assert附加了条件使得方程有唯一解，不过这种方法时间复杂度高且特殊情况不好处理。
依稀记得芜湖集训的时候听zzt说数学题不会就上BM解递推式乱搞
准确来说BM可以 $O(n^2)$ 求常系数线性递推式，正适合题设情况。
1 | from functools import reduce |